# class Tree:
#
#     def __init__(self):
#
#         self.left = None
#         self.right = None
#         self.data = None
#
#
# root = Tree()
#
# root.data = '中国'
#
# root.left = Tree()
#
# root.left.data = '河南'
#
# root.right = Tree()
#
# root.right.data = '北京'
#
# root.left.left = Tree()
# root.left.left.data = '安阳'
# root.right.right = Tree()
#
# root.right.right.data = '昌平'
#
# print(root.data)


class BSTnode:

    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None


class BST:

    def __init__(self):

        self.root = None

    def insert(self, val):

        newNode = BSTnode(val)

        if self.root is None:

            self.root = newNode

        else:

            curNode = self.root
            while True:
                # 进入左子树
                if val < curNode.val:

                    if curNode.left is None:
                        curNode.left = newNode
                        newNode.parent = curNode
                        break
                    curNode = curNode.left
                else:
                    # 进入右子树
                    if curNode.right is None:
                        curNode.right = newNode
                        newNode.parent = curNode
                        break
                    curNode = curNode.right

    def find(self, val):

        curNode = self.root

        while curNode is not None:
            if val < curNode.val:

                curNode = curNode.left
            elif val > curNode.val:

                curNode = curNode.right
            else:
                return True
        return False


mylist = [2, 3, 4, 5, 6, 7, 8, 9, 0]

bst = BST()

for x in range(len(mylist)):
    bst.insert(mylist[x])

print(bst.find(6))
